package linkedlist;

/**
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，
 * nodes 为节点总数。
 */
public class no328 {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null){
            return head;
        }
        ListNode beforeNode = new ListNode(-1);
        ListNode before = beforeNode;
        ListNode afterNode = new ListNode(-1);
        ListNode after = afterNode;
        ListNode cur = head;
        int count = 1;
        while (cur != null){
            if(count % 2 != 0){
                before.next = cur;
                before = before.next;
            }else{
                after.next = cur;
                after = after.next;
            }
            cur = cur.next;
            count++;
        }
        if(after != null){
            after.next = null;
        }
        before.next = afterNode.next;
        return beforeNode.next;
    }
}
